package com.ding.practice.algorithm.leetcode.hot100;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.List;

/**
 * 力扣热题100之最大水桶面积
 * @ID = 11
 * @date 2024年07月12日11:02:41
 *
 *给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
 *
 * 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
 *
 * 返回容器可以储存的最大水量。
 *
 * 说明：你不能倾斜容器。
 *
 * 输入：[1,8,6,2,5,4,8,3,7]
 * 输出：49
 * 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
 * 示例 2：
 *
 * 输入：height = [1,1]
 * 输出：1
 */
public class WaterMaxArea_11 {
    // 双循环，不是最优解
    public static int maxArea2(int[] height) {
        int maxArea = 0;
        int tempArea = 0;
        for(int i = 0;i < height.length ;i ++){
            for(int j = i+1;j < height.length ;j ++){
                tempArea = Math.min(height[i],height[j]) * (j - i);
                maxArea = Math.max(tempArea, maxArea);
            }
        }
        return maxArea;
    }
    // 双指针解法
    /*
    解题的关键点在于，定义两端指针，向内循环，移动最短的那根木桶，更优解是移动最短的那根后，移动到比最短的长的那根，再跟长的做比较
     */
    public static int maxArea(int[] height) {
        int leftPoint = 0;
        int rightPoint = height.length -1;
        int maxArea = minValue(height[leftPoint],height[rightPoint]) * (rightPoint - leftPoint);
        while (leftPoint != rightPoint -1){
            // 肯定不能移动长的那一端，因为移动长的那一端之后，木桶的高度取决于短的那一端，然后移动之后宽度还减少了，必然水会越来越少
            // 所以从两边移动的话，移动的是短的那一端
            if (height[leftPoint] > height[rightPoint]){
                rightPoint --;
            }else {
                leftPoint ++;
            }
            maxArea = maxValue(maxArea,(minValue(height[leftPoint],height[rightPoint]) * (rightPoint - leftPoint)));
        }
        return maxArea;
    }
    public static int minValue(int s1,int s2){
        return s1 < s2 ? s1 : s2;
    }
    public static int maxValue(int s1,int s2){
        return s1 > s2 ? s1 : s2;
    }
    public static int maxArea3(int[] height) {
        int l = 0;// 定义左指针
        int r = height.length - 1;// 定义右指针
        int maxarea = 0;// 定义最大面积
        while (l < r) {
            int minH = Math.min(height[l], height[r]);
            maxarea = Math.max(maxarea, (r - l) * minH);
            // 找到最短的那个后，去寻找比最短的长的那个，这样面积才可能会增加
            while (height[l] <= minH && l < r) {
                l++;
            }
            while (height[r] <= minH && l < r) {
                r--;
            }
        }
        return maxarea;
    }

    public static void main(String[] args) {
        int[] array = {1,8,6,2,5,4,8,3,7};
        // 预期结果49
        System.out.println(maxArea3(array));
    }

}
